package solver;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import model.Neighborhood;
import model.Process;
import model.Service;
import model.SolverEnvironment;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import util.ObjectIdPropertyPair;

import etm.core.configuration.EtmManager;
import etm.core.monitor.EtmMonitor;
import etm.core.monitor.EtmPoint;
import gurobi.GRBVar;

public class SelectionAgent4 {
	private static Logger log = LoggerFactory.getLogger(SelectionAgent4.class);
	// private static final EtmMonitor etmMonitor = EtmManager.getEtmMonitor();

	SolverEnvironment env;

	final static int factor = 2;

	boolean dependencyConstraintsNeeded = false;

	int limitXvars = -1;

	public SelectionAgent4(SolverEnvironment env) {
		this.env = env;
	}

	public void setLimitXvars(int limitXvars) {
		this.limitXvars = limitXvars;
	}

	public int getLimitXvars() {
		return limitXvars;
	}

	public void setDependencyConstraintsNeeded(
			boolean dependencyConstraintsNeeded) {
		this.dependencyConstraintsNeeded = dependencyConstraintsNeeded;
	}

	public List<Integer> selectFullRandomProcessesAndMachinesFast(int nop,
			int noem, int non) {
		// EtmPoint point = etmMonitor
		// .createPoint("SelectionAgent4:selectFullRandomProcessesAndMachinesFast");
		noem = noem * factor;
		nop = nop < env.problem.P ? nop : env.problem.P;
		noem = noem < env.problem.M ? noem : env.problem.M;
		List<Integer> selectedMachines = new ArrayList<Integer>();
		List<Integer> selectedNeighborHoods = RobertFloydSamplingAlgorithm(
				env.problem.N, non);
		List<Integer> ballotProcesses = new ArrayList<Integer>();
		for (Integer n_id : selectedNeighborHoods) {
			Neighborhood neighborhood = env.problem.getNeighborhoods()
					.get(n_id);
			int r = 0;
			if (selectedNeighborHoods.indexOf(n_id) == selectedNeighborHoods
					.size() - 1) {
				r = noem % non;
			}
			List<Integer> sel_mac = RobertFloydSamplingAlgorithm(neighborhood
					.getMachines().size(), noem / non + r);
			for (Integer machine_neighborhood_index : sel_mac) {
				int m_id = neighborhood.getMachines().get(
						machine_neighborhood_index);
				selectedMachines.add(m_id);
			}
		}

		selectedMachines = filterKeepingLoadedMachines(selectedMachines, noem
				/ factor);

		for (Integer m_id : selectedMachines) {
			ballotProcesses.addAll(env.getCurrentSolution()
					.getProcessesForMachine(m_id));
		}

		if (env.getRandom().nextDouble() < 0.95)
			ballotProcesses = filterKeepingHeavyProcesses(ballotProcesses, nop);

		List<Integer> selectedProcesses = new ArrayList<Integer>();
		for (Integer id : RobertFloydSamplingAlgorithm(ballotProcesses.size(),
				nop)) {
			Process aProcess = env.problem.getProcesses().get(
					ballotProcesses.get(id));
			selectedProcesses.add(aProcess.getId());
			aProcess.clearEligibleMachines();
			aProcess.setEligibleMachines(new ArrayList<Integer>(
					selectedMachines));
		}
		clearConflictConstraintsForFixedProcess(selectedProcesses);
		clearTransientConstraints(selectedProcesses);
		if (!dependencyConstraintsNeeded) {
			clearDependencies1(selectedProcesses);
			clearDependencies2(selectedProcesses);
		}
		reduceXVars(selectedProcesses);
		clearSelectedProcessesHavingOneEligibleMachine(selectedProcesses);
		logSubproblemStatistics(selectedProcesses);
		// point.collect();
		return selectedProcesses;
	}

	protected void logSubproblemStatistics(List<Integer> selectedProcesses) {
		int xvars = 0;
		Set<Integer> locations = new HashSet<Integer>();
		Set<Integer> neighborhoods = new HashSet<Integer>();
		Map<Integer, List<Integer>> services = new HashMap<Integer, List<Integer>>();
		Set<Integer> machines = new HashSet<Integer>();
		for (Integer p : selectedProcesses) {
			Process aProcess = env.getProblem().getProcesses().get(p);
			Integer s = aProcess.getService();
			if (!services.containsKey(s)) {
				List<Integer> aList = new ArrayList<Integer>();
				aList.add(p);
				services.put(s, aList);
			} else {
				services.get(s).add(p);
			}

			for (Integer m : aProcess.getEligibleMachines()) {
				locations.add(env.getProblem().getLocationIdForMachineId(m));
				neighborhoods.add(env.getProblem()
						.getNeighborhoodIdForMachineId(m));
				machines.add(m);
				xvars++;
			}
		}

		log.debug(String
				.format("PROCESSES=%d, MACHINES=%d, LOCATIONS=%d, NEIGHBORHOODS=%d, SERVICES=%s LIMITXVARS=%d XVARS=%d",
						selectedProcesses.size(), machines.size(),
						locations.size(), neighborhoods.size(),
						services.size(), limitXvars, xvars));
	}

	public List<Integer> selectFullRandomProcessesAndMachinesFast_ORIGINAL(
			int nop, int noem, int non) {
		// EtmPoint point = etmMonitor
		// .createPoint("SelectionAgent4:selectFullRandomProcessesAndMachinesFast");
		nop = nop < env.problem.P ? nop : env.problem.P;
		noem = noem < env.problem.M ? noem : env.problem.M;
		List<Integer> selectedMachines = new ArrayList<Integer>();
		List<Integer> selectedNeighborHoods = RobertFloydSamplingAlgorithm(
				env.problem.N, non);
		List<Integer> ballotProcesses = new ArrayList<Integer>();
		for (Integer n_id : selectedNeighborHoods) {
			Neighborhood neighborhood = env.problem.getNeighborhoods()
					.get(n_id);
			int r = 0;
			if (selectedNeighborHoods.indexOf(n_id) == selectedNeighborHoods
					.size() - 1) {
				r = noem % non;
			}
			List<Integer> sel_mac = RobertFloydSamplingAlgorithm(neighborhood
					.getMachines().size(), noem / non + r);
			for (Integer machine_neighborhood_index : sel_mac) {
				int m_id = neighborhood.getMachines().get(
						machine_neighborhood_index);
				selectedMachines.add(m_id);
				ballotProcesses.addAll(env.getCurrentSolution()
						.getProcessesForMachine(m_id));
			}
		}
		List<Integer> selectedProcesses = new ArrayList<Integer>();
		for (Integer id : RobertFloydSamplingAlgorithm(ballotProcesses.size(),
				nop)) {
			Process aProcess = env.problem.getProcesses().get(
					ballotProcesses.get(id));
			selectedProcesses.add(aProcess.getId());
			aProcess.clearEligibleMachines();
			aProcess.setEligibleMachines(new ArrayList<Integer>(
					selectedMachines));
		}
		clearConflictConstraintsForFixedProcess(selectedProcesses);
		clearTransientConstraints(selectedProcesses);
		if (!dependencyConstraintsNeeded) {
			clearDependencies1(selectedProcesses);
			clearDependencies2(selectedProcesses);
		}
		reduceXVars(selectedProcesses);
		clearSelectedProcessesHavingOneEligibleMachine(selectedProcesses);
		// point.collect();
		return selectedProcesses;
	}

	protected void reduceXVars(List<Integer> processes) {
		if (limitXvars != -1) {
			// order processes by eligible machines number
			List<Integer> p_ids_List = new ArrayList<Integer>();
			List<Integer> em_ids_List = new ArrayList<Integer>();

			for (Integer p : processes) {
				Process aProcess = env.getProblem().getProcesses().get(p);
				int cm = env.getCurrentSolution().getMachineIdForProcessId(p);
				if (aProcess.getEligibleMachines().size() > 2) {
					for (Integer m : aProcess.getEligibleMachines()) {
						if (m != cm) {
							p_ids_List.add(p);
							em_ids_List.add(m);
						}
					}
				}
			}
			int N = p_ids_List.size();
			int M = N - limitXvars + processes.size();
			if (N >= M) {
				List<Integer> choosenValues = RobertFloydSamplingAlgorithm(N, M);
				for (Integer i_obj : choosenValues) {
					Process aProcess = env.getProblem().getProcesses()
							.get(p_ids_List.get(i_obj));
					aProcess.removeElligibleMachine(em_ids_List.get(i_obj));
					// log.debug(String.format(
					// "Process %d machine %d removed due to XVARS limit",
					// aProcess.getId(), em_ids_List.get(i_obj)));
				}
			}
		}
	}

	protected List<Integer> RobertFloydSamplingAlgorithm(int N, int M) {
		if (M > N)
			M = N;
		List<Integer> samples = new ArrayList<Integer>();
		for (int j = N - M + 1; j <= N; j++) {
			int t = env.random.nextInt(j);
			if (!samples.contains(t))
				samples.add(t);
			else
				samples.add(j - 1);
		}
		return samples;
	}

	protected void clearDependencies1(List<Integer> selectedProcesses) {
		for (Integer p_id : selectedProcesses) {
			Process selectedProcess = env.getProblem().getProcesses().get(p_id);
			int sa_index = env.getProblem().getServiceIdForProcessId(p_id);
			Service sa = env.getProblem().getServices().get(sa_index);
			if (soleProcessFromServiceInItsNeighborhood(selectedProcess)
					&& !sa.getDependedBy().isEmpty()) {
				int c_n = env.getCurrentSolution().getNeighBorhoodIdForProcess(
						p_id);
				List<Integer> to_be_removed = new ArrayList<Integer>();
				for (Integer m : selectedProcess.getEligibleMachines()) {
					if (env.getProblem().getNeighborhoodIdForMachineId(m) != c_n) {
						to_be_removed.add(m);
						// log.debug(String
						// .format("CLEAR DEPENDENCY CONSTRAINT TYPE1: Process %d machine %d removed",
						// p_id, m));
					}
				}
				selectedProcess.removeElligibleMachines(to_be_removed);
			}
		}
	}

	protected void clearDependencies2(List<Integer> selectedProcesses) {
		for (Integer p_id : selectedProcesses) {
			Process selectedProcess = env.getProblem().getProcesses().get(p_id);
			int sa_index = env.getProblem().getServiceIdForProcessId(p_id);
			Service sa = env.getProblem().getServices().get(sa_index);
			List<Integer> to_be_removed = new ArrayList<Integer>();
			for (Integer m : selectedProcess.getEligibleMachines()) {
				int n_id = env.getProblem().getNeighborhoodIdForMachineId(m);
				boolean flag1 = true;
				for (Integer sb_index : sa.getDependsOn()) {
					Service sb = env.getProblem().getServices().get(sb_index);
					boolean flag2 = false;
					for (Integer p_id2 : sb.getProcesses()) {
						// if (!isFixed(selectedProcesses, p_id2))
						// continue;
						int n_id2 = env.getCurrentSolution()
								.getNeighBorhoodIdForProcess(p_id2);
						if (n_id2 == n_id) {
							flag2 = true;
							break;
						}
					}
					if (flag2 == false) {
						flag1 = false;
						break;
					}
				}
				if (flag1 == false) {
					to_be_removed.add(m);
					// log.debug(String
					// .format("CLEAR DEPENDENCY CONSTRAINT TYPE2: Process %d machine %d removed",
					// p_id, m));
				}
			}
			selectedProcess.removeElligibleMachines(to_be_removed);
		}
	}

	private boolean soleProcessFromServiceInItsNeighborhoodFast(
			Process selectedProcess) {
		Service sa = env.getProblem().getServices()
				.get(selectedProcess.getService());
		int n_id = env.getCurrentSolution().getNeighBorhoodIdForProcess(
				selectedProcess.getId());
		if (env.getCurrentSolution().serviceProcessesPerNeighborhood[sa.getId()][n_id] == 1)
			return true;
		else
			return false;
	}

	private boolean soleProcessFromServiceInItsNeighborhood(
			Process selectedProcess) {
		Service sa = env.getProblem().getServices()
				.get(selectedProcess.getService());
		int n_id = env.getCurrentSolution().getNeighBorhoodIdForProcess(
				selectedProcess.getId());
		for (Integer p_id : sa.getProcesses()) {
			if (p_id == selectedProcess.getId())
				continue;
			int n_id2 = env.getCurrentSolution().getNeighBorhoodIdForProcess(
					p_id);
			if (n_id == n_id2)
				return false;
		}
		return true;
	}

	@Deprecated
	private boolean isFixed(List<Integer> selectedProcesses, Integer p_id2) {
		Process aProcess = env.getProblem().getProcesses().get(p_id2);
		int m_id = env.getCurrentSolution().getMachineIdForProcessId(p_id2);
		if ((selectedProcesses.contains(p_id2))
				&& (aProcess.getEligibleMachines().contains(new Integer(m_id))))
			return false;
		else
			return true;
	}

	// Selected processes should not have as eligible machines machines that
	// already have another process of the same service that could not be moved.
	protected void clearConflictConstraintsForFixedProcess(
			List<Integer> selectedProcesses) {
		for (Integer p_id : selectedProcesses) {
			Process selectedProcess = env.problem.getProcesses().get(p_id);
			int s_id = env.problem.getServiceIdForProcessId(p_id);
			for (Integer p_id2 : env.problem.getProcessesIdsForServiceId(s_id)) {
				if (p_id == p_id2)
					continue;
				if (selectedProcesses.contains(p_id2))
					continue;
				int m_id = env.getCurrentSolution().getMachineIdForProcessId(
						p_id2);
				if (selectedProcess.getEligibleMachines().contains(
						new Integer(m_id))) {
					selectedProcess.removeElligibleMachine(m_id);
					// log.debug(String
					// .format("Process p%d_s%d machine m%d removed because p%d_%d of the same service is scheduled in it",
					// p_id, s_id, m_id, p_id2, s_id));
				}
			}
			if (selectedProcess.getEligibleMachines().isEmpty()) {
				throw new IllegalStateException(
						"selected process should have at least 1 eligible machine");
			}
		}
	}

	protected void clearTransientConstraints(List<Integer> selectedProcesses) {
		for (Integer p : selectedProcesses) {
			Process aProcess = env.problem.getProcesses().get(p);
			List<Integer> to_be_removed = new ArrayList<Integer>();
			for (Integer m : aProcess.getEligibleMachines())
				if (env.getIllegalMachines(p).contains(m))
					to_be_removed.add(m);
			if (!to_be_removed.isEmpty()) {
				aProcess.removeElligibleMachines(to_be_removed);
				// log.debug(String
				// .format("Process %d machines removed due to transient constraint %s",
				// p, to_be_removed));
			}
		}
	}

	protected void clearSelectedProcessesHavingOneEligibleMachine(
			List<Integer> selectedProcesses) {
		List<Integer> processesWithOnlyOneEligibleMachine = new ArrayList<Integer>();
		for (Integer p : selectedProcesses) {
			if (env.problem.getEligibleMachinesFor(p).size() <= 1)
				processesWithOnlyOneEligibleMachine.add(p);
		}
		if (!processesWithOnlyOneEligibleMachine.isEmpty()) {
			// log.debug("The following processes have only one eligible machine so they are eliminated: "
			// + processesWithOnlyOneEligibleMachine);
			selectedProcesses.removeAll(processesWithOnlyOneEligibleMachine);
		}

	}

	public List<Integer> selectAllProcessesForMachines(
			List<Integer> selectedMachines, int process_limit) {
		List<Integer> selectedProcesses = new ArrayList<Integer>();
		for (Integer m_id : selectedMachines) {
			for (Integer p_id : env.getCurrentSolution()
					.getProcessesForMachine(m_id)) {
				Process aProcess = env.getProblem().getProcesses().get(p_id);
				aProcess.clearEligibleMachines();
				aProcess.setEligibleMachines(new ArrayList<Integer>(
						selectedMachines));
				selectedProcesses.add(p_id);
			}
		}
		clearConflictConstraintsForFixedProcess(selectedProcesses);
		clearTransientConstraints(selectedProcesses);
		clearSelectedProcessesHavingOneEligibleMachine(selectedProcesses);
		int SPS = selectedProcesses.size();
		if ((process_limit == -1) || (SPS <= process_limit))
			return selectedProcesses;
		else {
			Collections.shuffle(selectedProcesses, env.getRandom());
			for (int i = 0; i < SPS - process_limit; i++) {
				selectedProcesses.remove(0);
			}
			return selectedProcesses;
		}
	}

	protected List<Integer> filterKeepingLoadedMachines(
			List<Integer> selectedMachines, int machines_to_keep) {
		env.getCurrentSolution().refreshLoadCostContribution(selectedMachines);
		env.getCurrentSolution().refreshBalanceCostContribution(
				selectedMachines);

		long[] cost_per_machine = new long[selectedMachines.size()];
		int i = 0;
		for (Integer m_id : selectedMachines) {
			cost_per_machine[i] = (env.getCurrentSolution().load_cost_contribution_zipped[m_id] + env
					.getCurrentSolution().balance_cost_contribution_zipped[m_id]);
			i++;
		}

		sort(selectedMachines, cost_per_machine);

		int SM = selectedMachines.size();
		if (SM >= factor * machines_to_keep) {
			for (int k = 0; k < SM / (factor * 2); k++) {
				selectedMachines.remove(selectedMachines.size() / 2);
			}
		}

		List<Integer> new_selected_machines = new ArrayList<Integer>();
		for (Integer x : RobertFloydSamplingAlgorithm(selectedMachines.size(),
				machines_to_keep)) {
			new_selected_machines.add(selectedMachines.get(x));
		}

		return new_selected_machines;
	}

	private List<Integer> filterKeepingHeavyProcesses(
			List<Integer> ballotProcesses, int nop) {
		int before = ballotProcesses.size();
		long[] resource_demands = new long[ballotProcesses.size()];
		int selectedR = env.getRandom().nextInt(env.getProblem().RE);
		int i = 0;
		for (Integer p : ballotProcesses) {
			resource_demands[i] = env.getProblem().getR(p, selectedR);
			i++;
		}
		sort(ballotProcesses, resource_demands);
		int removals = ballotProcesses.size() - 2 * nop;
		for (int k = 0; k < removals; k++) {
			ballotProcesses.remove(0);
		}
		// int after = ballotProcesses.size();
		// log.debug(String.format("Processes before=%d after=%d", before,
		// after));
		return ballotProcesses;
	}

	// a simple bubble sort for starters
	protected void sort(List<Integer> selectedMachines, long[] cost) {
		for (int i = 1; i < cost.length; i++) {
			for (int j = cost.length - 1; j >= i; j--) {
				if (cost[j - 1] > cost[j]) {
					long temp1 = cost[j];
					cost[j] = cost[j - 1];
					cost[j - 1] = temp1;

					Integer temp2 = selectedMachines.get(j);
					selectedMachines.set(j, selectedMachines.get(j - 1));
					selectedMachines.set(j - 1, temp2);
				}
			}
		}
	}

	public void changeLimitXVarsByPercent(double d) {
		limitXvars = (int) (limitXvars + d * limitXvars);
	}

}
